迷宮生成 用演算法（DFS, Prim’s, Kruskal’s, Recursive Division 等）自動生成隨機迷宮。 支援不同大小、難度，甚至加入「陷阱」「寶藏」「NPC」。 AI 尋路 用 BFS / A* 找到 最短路徑。 過程中紀錄每個節點、轉折點與關鍵位置（例如分岔、死路、捷徑）。 敘事化輸出 (GAI) 把最短路徑資料丟給生成模型： 冒險敘事 → 把路徑描述成一場冒險故事：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <getopt.h>
#include <math.h>

typedef struct {
    int r, c;
} Point;

typedef struct {
    int h, w;
    int **grid;  // 0=wall, 1=path
} Maze;

// ---------------- Utilities ----------------
int in_bounds(Point p, int h, int w) {
    return p.r >= 0 && p.r < h && p.c >= 0 && p.c < w;
}

Point neighbors4[4] = { { -1,0 }, { 1,0 }, {0,-1}, {0,1} };

// ---------------- Maze init ----------------
Maze *create_maze(int h, int w) {
    Maze *m = malloc(sizeof(Maze));
    m->h = h; m->w = w;
    m->grid = malloc(sizeof(int*) * h);
    for (int i=0;i<h;i++) {
        m->grid[i] = calloc(w,sizeof(int));
    }
    return m;
}

void free_maze(Maze *m) {
    for (int i=0;i<m->h;i++) free(m->grid[i]);
    free(m->grid);
    free(m);
}

void set_cell(Maze *m, Point p, int val) {
    m->grid[p.r][p.c] = val;
}

// ---------------- DFS Maze generation ----------------
void carve_dfs(Maze *maze, int seed) {
    srand(seed);
    Point start = {1,1};
    set_cell(maze,start,1);
    Point stack[10000]; int top=0;
    stack[top++] = start;

    while (top>0) {
        Point cur = stack[top-1];
        Point candidates[4]; int cnt=0;
        int dirs[4][2] = {{-2,0},{2,0},{0,-2},{0,2}};
        for (int i=0;i<4;i++) {
            Point np = {cur.r+dirs[i][0], cur.c+dirs[i][1]};
            if (in_bounds(np,maze->h,maze->w) && maze->grid[np.r][np.c]==0) {
                candidates[cnt++] = np;
            }
        }
        if (cnt>0) {
            Point nxt = candidates[rand()%cnt];
            Point mid = { (cur.r+nxt.r)/2, (cur.c+nxt.c)/2 };
            set_cell(maze, mid, 1);
            set_cell(maze, nxt, 1);
            stack[top++] = nxt;
        } else {
            top--;
        }
    }
}

// ---------------- BFS ----------------
typedef struct Node {
    Point p;
    int g;
    struct Node *prev;
} Node;

typedef struct {
    Node **arr;
    int size, cap;
} Queue;

Queue* q_create(int cap) {
    Queue* q = malloc(sizeof(Queue));
    q->arr = malloc(sizeof(Node*)*cap);
    q->size=0; q->cap=cap;
    return q;
}
void q_push(Queue* q, Node* n) { q->arr[q->size++] = n; }
Node* q_pop(Queue* q) {
    Node* n = q->arr[0];
    for (int i=1;i<q->size;i++) q->arr[i-1]=q->arr[i];
    q->size--;
    return n;
}
int q_empty(Queue* q) { return q->size==0; }

Node* bfs(Maze *maze, Point start, Point goal) {
    int h=maze->h, w=maze->w;
    int visited[h][w]; memset(visited,0,sizeof(visited));
    Queue* q = q_create(h*w);
    Node* startNode = malloc(sizeof(Node)); startNode->p=start; startNode->g=0; startNode->prev=NULL;
    q_push(q,startNode);
    visited[start.r][start.c]=1;
    Node* found=NULL;

    while (!q_empty(q)) {
        Node* cur = q_pop(q);
        if (cur->p.r==goal.r && cur->p.c==goal.c) { found=cur; break; }
        for (int i=0;i<4;i++) {
            Point np = {cur->p.r+neighbors4[i].r, cur->p.c+neighbors4[i].c};
            if (in_bounds(np,h,w) && maze->grid[np.r][np.c]==1 && !visited[np.r][np.c]) {
                Node* nxt = malloc(sizeof(Node));
                nxt->p=np; nxt->g=cur->g+1; nxt->prev=cur;
                q_push(q,nxt);
                visited[np.r][np.c]=1;
            }
        }
    }
    return found;
}

// ---------------- ASCII dump ----------------
void dump_ascii(Maze *maze, Node* path, Point start, Point goal) {
    int h=maze->h, w=maze->w;
    int mark[h][w]; memset(mark,0,sizeof(mark));
    for (Node* n=path;n;n=n->prev) mark[n->p.r][n->p.c]=1;
    for (int r=0;r<h;r++) {
        for (int c=0;c<w;c++) {
            Point p={r,c};
            if (p.r==start.r && p.c==start.c) printf("S");
            else if (p.r==goal.r && p.c==goal.c) printf("G");
            else if (mark[r][c]) printf("*");
            else printf(maze->grid[r][c]==1?" ":"#");
        }
        printf("\n");
    }
}

// ---------------- Narrative ----------------
void narrative(Node* path, Point start, Point goal) {
    printf("\n--- Narrative ---\n");
    int step=0;
    for (Node* n=path;n;n=n->prev) step++;
    printf("從入口 (%d,%d) 出發，目標在 (%d,%d)，共 %d 步。\n", 
        start.r,start.c,goal.r,goal.c,step);
    int i=1;
    for (Node* n=path;n;n=n->prev) {
        printf("第 %d 步: 到達 (%d,%d)\n", step-i+1, n->p.r, n->p.c);
        i++;
    }
}

// ---------------- main ----------------
int main(int argc, char** argv) {
    int w=21,h=15,seed=time(NULL);
    char algo[20]="dfs";

    int opt;
    while ((opt=getopt(argc,argv,""))!=-1) { }

    Maze* maze = create_maze(h,w);
    carve_dfs(maze,seed);
    Point start={1,1};
    Point goal={h-2,w-2};

    Node* path = bfs(maze,start,goal);
    dump_ascii(maze,path,start,goal);
    narrative(path,start,goal);

    free_maze(maze);
    return 0;
}

輸出
#####################
#S# ###
##############
#######
################
#### ##
############# ####
#### ##
######### # ####
#### # ##
###### #### ######
#**# ## ## #
########### # ## #

*******# # **G#

#####################

--- Narrative ---

已將詳細紀錄輸出到 maze_log.json

執行
現在
#####################
#S******# # #
#######*# # # ##### #

# #*# # # # #

# # #*# # # # # #

# #*# # # # #

### #*# ### # # #

# # #*# # # # #

#$# #*### # # #

# #***# # #

#######*# #######

#T # ## #**# #

# # # #######*#

# # *******#**G#

#####################

--- Narrative ---
=== 迷宮冒險 (dfs) ===
從 Point(r=1, c=1) 出發，目標抵達 Point(r=13, c=19)。共 35 步。
熱浪翻滾，迷宮中還留有古老符文的餘溫。
第 1 步：來到 Point(r=1, c=1). 從入口踏入。 這裡曾經是死路的轉角，你來回確認過路徑。
第 2 步：來到 Point(r=1, c=2). 你快步前進，目光搜尋四周。
第 3 步：來到 Point(r=1, c=3). 你小心前進，腳步輕柔。
第 4 步：來到 Point(r=1, c=4). 你快步前進，目光搜尋四周。
第 5 步：來到 Point(r=1, c=5). 你聽到遠處傳來複雜的聲響，保持警惕。
第 6 步：來到 Point(r=1, c=6). 你聽到遠處傳來複雜的聲響，保持警惕。
第 7 步：來到 Point(r=1, c=7). 你聽到遠處傳來複雜的聲響，保持警惕。 你轉彎，視野改變，新的通道顯現。
第 8 步：來到 Point(r=2, c=7). 你聽到遠處傳來複雜的聲響，保持警惕。
第 9 步：來到 Point(r=3, c=7). 你快步前進，目光搜尋四周。
第 10 步：來到 Point(r=4, c=7). 你聽到遠處傳來複雜的聲響，保持警惕。
第 11 步：來到 Point(r=5, c=7). 你快步前進，目光搜尋四周。
第 12 步：來到 Point(r=6, c=7). 你聽到遠處傳來複雜的聲響，保持警惕。
第 13 步：來到 Point(r=7, c=7). 你快步前進，目光搜尋四周。
第 14 步：來到 Point(r=8, c=7). 你聽到遠處傳來複雜的聲響，保持警惕。
第 15 步：來到 Point(r=9, c=7). 你小心前進，腳步輕柔。 你轉彎，視野改變，新的通道顯現。
第 16 步：來到 Point(r=9, c=8). 你聽到遠處傳來複雜的聲響，保持警惕。
第 17 步：來到 Point(r=9, c=9). 你聽到遠處傳來複雜的聲響，保持警惕。 你轉彎，視野改變，新的通道顯現。
第 18 步：來到 Point(r=10, c=9). 你快步前進，目光搜尋四周。
第 19 步：來到 Point(r=11, c=9). 你快步前進，目光搜尋四周。
第 20 步：來到 Point(r=12, c=9). 你聽到遠處傳來複雜的聲響，保持警惕。
第 21 步：來到 Point(r=13, c=9). 你聽到遠處傳來複雜的聲響，保持警惕。 這裡是一個分岔路口，你必須選擇方向。 你轉彎，視野改變，新的通道顯現。
第 22 步：來到 Point(r=13, c=10). 你快步前進，目光搜尋四周。
第 23 步：來到 Point(r=13, c=11). 你聽到遠處傳來複雜的聲響，保持警惕。
第 24 步：來到 Point(r=13, c=12). 你快步前進，目光搜尋四周。
第 25 步：來到 Point(r=13, c=13). 你小心前進，腳步輕柔。
第 26 步：來到 Point(r=13, c=14). 你聽到遠處傳來複雜的聲響，保持警惕。
第 27 步：來到 Point(r=13, c=15). 你聽到遠處傳來複雜的聲響，保持警惕。 你轉彎，視野改變，新的通道顯現。
第 28 步：來到 Point(r=12, c=15). 你小心前進，腳步輕柔。
第 29 步：來到 Point(r=11, c=15). 你快步前進，目光搜尋四周。 你轉彎，視野改變，新的通道顯現。
第 30 步：來到 Point(r=11, c=16). 你聽到遠處傳來複雜的聲響，保持警惕。
第 31 步：來到 Point(r=11, c=17). 你快步前進，目光搜尋四周。 你轉彎，視野改變，新的通道顯現。
第 32 步：來到 Point(r=12, c=17). 你快步前進，目光搜尋四周。
第 33 步：來到 Point(r=13, c=17). 你小心前進，腳步輕柔。 你轉彎，視野改變，新的通道顯現。
第 34 步：來到 Point(r=13, c=18). 你聽到遠處傳來複雜的聲響，保持警惕。
第 35 步：來到 Point(r=13, c=19). 你到達終點，勝利就在眼前。
在最後一刻，你用智慧與勇氣克服障礙，故事的結局由你書寫。